package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.ListNode;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author 覃国强
 * @date 2022-05-19 18:18
 */
public class 题库_0023_合并K个升序链表 {

  static
  class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
      if (lists == null || lists.length == 0) {
        return null;
      }
      ListNode dummy = new ListNode();
      ListNode tail = dummy;
      PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(node -> node.val));
      for (ListNode node : lists) {
        if (node != null) {
          priorityQueue.add(node);
        }
      }

      while (!priorityQueue.isEmpty()) {
        ListNode node = priorityQueue.remove();
        tail.next = node;
        tail = tail.next;
        if (node.next != null) {
          priorityQueue.add(node.next);
        }
      }

      return dummy.next;
    }
  }

}
